首先需要知道两个定理:

1、费马小定理：假如$p$是素数，且$\gcd(a,p)=1$，那么 $a(p-1)≡1(\text{mod}\ p)$。不知所云的萌新请点击此处‍自行脑补一下

2、二次探测定理：如果$p$是素数，$x$是小于$p$的正整数，那么要么$x=1$，要么$x=p-1$。

　　证明：这是显然的，因为相当于$p$能整除$(x+1)(x-1)$。

　　由于$p$是素数，那么只可能是$x-1$能被p整除(此时x=1) 或 x+1能被p整除(此时x=p-1)。

接着，如果$a^{n-1} ≡ 1 (\text{mod} n)$成立，Miller-Rabin算法不是立即找另一个$a$进行测试，而是看$n-1$是不是偶数。如果$n-1$是偶数，另$u=\dfrac{n-1}{2}$，并检查是否满足二次探测定理即$a^u ≡ 1$ 或$ a^u ≡ n - 1(\text{mod}\ n)$。

算法实现

Miller-Rabin算法随机生成底数$a$，进行多次调用函数进行测试，Miller-Rabin检测也存在伪素数的问题，但是与费马检测不同，MR检测的正确概率不依赖被检测数$p$，而仅依赖于检测次数。已经证明，如果一个数$p$为合数，那么Miller-Rabin检测的证据数量不少于比其小的正整数的$\dfrac{3}{4}p$，换言之，$k$次检测后得到错误结果的概率为$\left (\dfrac{1}{4} \right )^k$。我们在实际应用中一般可以测试$15\sim20$次。

代码：

#include <iostream>
#include <cmath>
using namespace std;

long long qpow(int a, int b, int r)
{
	long long ans = 1, buff = a;
	while (b)
	{
		if (b & 1)ans = (ans * buff) % r;
		buff = (buff * buff) % r;
		b >>= 1;
	}
	return ans;
}
bool Miller_Rabbin(int n, int a)
{
	int r = 0, s = n - 1, j;
	if (!(n%a))
		return false;
	while (!(s & 1))
	{
		s >>= 1;
		r++;
	}
	long long k = qpow(a, s, n);
	if (k == 1)
		return true;
	for (j = 0; j < r; j++, k = k * k % n)
		if (k == n - 1)
			return true;
	return false;
}
bool IsPrime(int n)
{
	int tab[] = { 2,3,5,7 };
	for (int i = 0; i < 4; i++)
	{
		if (n == tab[i])
			return true;
		if (!Miller_Rabbin(n, tab[i]))
			return false;
	}
	return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
	long long n;
	while (1)
	{
		cin >> n;
		cout << IsPrime(n) << endl;
	}
	return 0;
}